function quickSort(nums, left = 0, right = nums.length - 1) {
  if (left >= right) {
    return nums;
  }
  
// 选择区间里的随机元素作为基准
  const randomIndex = getRandomInt(left, right);
  [nums[left], nums[randomIndex]] = [nums[randomIndex], nums[left]];

  const pivot = nums[left];

  let lt = left + 1; // lt: less than
  let gt = right; // gt: greater than
  // all in nums[left + 1 ... lt) < pivot
  // all in nums[lt ... i) === pivot
  // all in nums(gt ... right] > pivot
  let i = left + 1;

  while (i <= gt) {
    if (nums[i] < pivot) {
      [nums[lt], nums[i]] = [nums[i], nums[lt]];
      lt++;
      i++;
    } else if (nums[i] === pivot) {
      i++;
    } else {
      // nums[i] > pivot
      [nums[gt], nums[i]] = [nums[i], nums[gt]];
      gt--;
    }
  }

  // 交换 nums[left] 和 nums[lt - 1]
  [nums[left], nums[lt - 1]] = [nums[lt - 1], nums[left]];

  quickSort(nums, left, lt - 2);
  quickSort(nums, gt + 1, right);
  return nums;
}

// 返回 [min, max] 之间的随机整数
function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

// 测试用例
const testCases = [
  [],
  [1],
  [5, 3, 8, 4, 2],
  [10, 9, 8, 7, 6, 5],
  [1, 2, 3, 4, 5],
  [3, 3, 3, 3],
  [5, -1, 0, 2, -3, 8]
];

for (const arr of testCases) {
  console.log(`原数组: [${arr}] => 排序后: [${quickSort(arr)}]`);
}